package sort

import (
	"fmt"
	"math"
)

var count int //测试计数用

//快速排序是冒泡排序的升级，属于交换排序类型
//时间复杂度N*O(logN)，空间复杂度O(logN)。空间复杂度是递归造成的。不稳定排序。
func QuickSort(arr []int) {
	count = 0
	quickSortHelper(arr, 0, len(arr)-1)

	//log
	l := float64(len(arr))
	fmt.Print(count, int(l*math.Log2(l)))
}

func quickSortHelper(arr []int, low int, high int) {
	if low < high {
		//partition,最终实现比基准值小的都在左边,比基准值大的都在右边
		pivotKey := partition(arr, low, high) //partition结束,基准值需重新设置为中间的位置

		//继续递归
		//注意点: 两个递归high和low的取值。因为基准值本身不属于两侧，是不需要再处理的，故需要-1和+1
		quickSortHelper(arr, low, pivotKey-1)
		quickSortHelper(arr, pivotKey+1, high)
	}
}

//优化2：尾递归优化,减少空间复杂度
func quickSortHelper2(arr []int, low int, high int) {
	for low < high {
		pivotKey := partition(arr, low, high)
		quickSortHelper(arr, low, pivotKey-1)

		//正常是对右侧进行递归，我们改成迭代
		low = pivotKey + 1 //这样下一次循环就会对新的[low,high]区间进行分区，等同于递归
	}
}

func partition(arr []int, low int, high int) int {
	//优化1:确保选择合适的中间值
	//mid := low + (high-low)/2
	////保证左端比较小
	//if arr[low] > arr[high] {
	//	arr[low], arr[high] = arr[high], arr[low]
	//}
	////保证中间比较小
	//if arr[mid] > arr[high] {
	//	arr[mid], arr[high] = arr[high], arr[mid]
	//}
	////保证左端比较小
	//if arr[low] > arr[mid] {
	//	arr[low], arr[mid] = arr[mid], arr[low]
	//}
	//优化1结束

	//分区开始
	//选基准值
	pivot := arr[low]
	//两侧逼近
	i, j := low, high //注意点: 必须重新赋值,否则会修改low和high的值
	for i < j {
		//注意点: 需要先从右边开始,因为选的是左边第一个为基准值。考虑一个极端的例子，右侧的元素都比左侧小，如果先从左侧开始，i++结束后面就不会再比较了。
		//右边开始,大于基准值则继续往左移动
		for i < j && arr[j] >= pivot {
			j--
			count++
		}
		//跳出了上面的循环，说明找到了一个比基准值小的值,需要放到基准值左边
		arr[i], arr[j] = arr[j], arr[i]

		//左边开始,小于基准值则继续往右移动
		for i < j && arr[i] <= pivot {
			i++
			count++
		}
		//跳出了上面的循环，说明找到了一个比基准值大的值,需要放到基准值右边
		arr[i], arr[j] = arr[j], arr[i]
	}

	//此时i=j
	return i
}
